Sau quá trình tu học dài hạn, Phó tế Anphong Nguyễn Hữu Long đã được thụ phong linh mục ngày 29 tháng 12 năm 1990. Tân linh mục chọn cho mình châm ngôn: "Tình yêu Đức Kitô thôi thúc tôi".[17][18] Sau khi được phong chức linh mục, linh mục Long được bổ nhiệm đảm trách vai trò linh mục phó giáo xứ Tam Kỳ, Đà Nẵng. Năm 1994, ông được cho đi du học tại Pháp và tốt nghiệp Cao học Giáo luật tại Học viện Công giáo Paris. Sau quá trình du học, năm 1999, linh mục Long trở về Việt Nam và được bổ nhiệm giữ vai trò quản nhiệm giáo xứ Hà Lam, Giáo phận Đà Nẵng trong thời gian ngắn, đến năm khoảng năm 2000 – 2001. Sau đó, linh mục Long đảm nhận vai trò linh mục chính xứ giáo xứ Trà Kiệu, thuộc Giáo phận Đà Nẵng và giữ chức vụ này đến năm 2003.[11][17][19][20]

Năm 2003, linh mục Nguyễn Hữu Long gia nhập Hội Linh mục Xuân Bích (PSS). Trong khoảng tám năm, từ năm 2003 đến năm 2011, ông đảm nhận vai trò linh mục linh hướng và Giáo sư các môn: Giáo luật, Giáo sử và Huấn giáo tại Đại chủng viện Huế.[17]

Trong khoảng thời gian từ năm 2011 đến tháng 9 năm 2013, linh mục Long đảm nhận vai trò Giám đốc Đại chủng viện Huế.[17] Cũng trong thời kỳ này, linh mục Long được Tổng giám mục Tổng giáo phận Huế Stêphanô Nguyễn Như Thể chọn làm thành viên ban đón tiếp phái đoàn Tòa án Giáo phận Rôma đến Tổng giáo phận Huế đầu tháng 4 năm 2012 để tìm gặp các nhân chứng về cố Hồng y Phanxicô Xaviê Nguyễn Văn Thuận và lắng nghe họ.[21]